﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmThinks.DynamicProgramming
{
    /// <summary>
    /// 最长公共子串
    /// </summary>
    public class LongestCommonSubstring
    {
        public static string Action1(string s1, string s2)
        {
            if (s1 == null || s2 == null)
            {
                return "";
            }

            #region 将字符长度较长的定义为s1 较短的定义为s2
            if (s1.Equals(s2))
            {
                return s1;
            }
            if (s1.Length < s2.Length)
            {
                var t = s1;
                s1 = s2;
                s2 = t;
            }
            #endregion

            int l1 = s1.Length;
            int l2 = s2.Length;
            int minLength = l2;//字符串最长长度
            int max = l1;
            List<string> strList = new List<string>();//候选公共字符串
            
            string st1="";
            string st2 = "";

            for (var i = 0; i < l1+l2-1; i++)
            {
                if (i < minLength)
                {
                    st1 = s1.Substring(0, i + 1);
                    st2 = s2.Substring(l2 - (i + 1));
                    strList.Add(GetCommonStr(st1, st2));
                    continue;
                }

                if (i <= max - 1)
                {
                    st1 = s1.Substring(i - minLength + 1, minLength );
                    st2 = s2;
                    strList.Add(GetCommonStr(st1, st2));
                    continue;
                }
                if (i > max - 1)
                {
                    st1 = s1.Substring(i - minLength + 1);
                    st2 = s2.Substring(0, l2 -1- (i  - max));
                    strList.Add(GetCommonStr(st1, st2));
                    continue;
                }
            }
            return strList.OrderByDescending(x => x.Length).FirstOrDefault() ?? "";


            
        }
        /// <summary>
        /// 比较两个字符串是否相等
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        private static string GetCommonStr(string str1,string str2)
        {
            #region 获取两字符传中相同的字符
            char[] chars = new char[str1.Length];
            for(int i = 0; i < str1.Length; i++)
            {
                if (str1[i] == str2[i])
                {
                    chars[i] = str1[i];
                }
            }
            #endregion

            string strTemp = "";
            List<char> temp = new List<char>();
            List<string> strs = new List<string>();

            bool clearFlag = false;//是否清除缓存数据
            for (int i = 0; i <chars.Length; i++)
            {
                strTemp = "";
                if (chars[i] != 0)
                {
                    if (clearFlag)
                    {
                        strTemp = new string(temp.ToArray<char>());
                        if (strTemp != "")
                        {
                            strs.Add(strTemp);
                        }
                        temp = new List<char>();
                        clearFlag = false;
                    }
                    temp.Add(chars[i]);
                }
                else
                {
                    clearFlag = true;
                }  
            }

            strTemp = new string(temp.ToArray<char>());
            if (strTemp != "")
            {
                strs.Add(strTemp);
            }

            return strs.OrderByDescending(x => x.Length).FirstOrDefault()??"";

        }
    }
}
